package a10_动态规划;

import java.util.Arrays;

/**
 * <p>
 * a16_目标和复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/2/13
 */
public class a16_目标和复习1 {
    public static void main(String[] args) {
        int targetSumWays = findTargetSumWays(new int[]{1}, 2);
        System.out.println();
    }
    //nums=[1,1,1,1,1]  target=3
    //leftNum + rightNum = sum
    //leftNum - rightNum = target
    //leftNum - (sum - leftNum) = target
    //leftNum = (sum + target) / 2
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if((sum + target) % 2 != 0){
            return 0;
        }
        int leftNum = Math.max( (sum + target) / 2,  sum - (sum + target) / 2);//保证为正数

        //题目变成了 促成leftNum有多少种方式
        //dp[j]:促成j有dp[j]种方式
        //递推公式：dp[j] = dp[j] + dp[j-nums[i]]

        int[] dp = new int[leftNum+1];
        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = leftNum; j >= nums[i]; j--) {//如果重量少于i对应的重量，那肯定就是dp[j]了
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        return dp[leftNum];
    }
}
